class Solution {
public:
    int longestValidParentheses(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.length() <= 1) {
            return 0;
        }
        int n = s.length();
        vector<int> dp(n, 0);
        int ans = 0;

        for (int i = 1; i < n; ++i) {
            if (s[i] == '(') {
                dp[i] = 0;
            } else {
                int pos = i - 1 - dp[i - 1];
                if (pos >= 0 && s[pos] == '(') {
                    dp[i] = i - pos + 1;
                    if (i - dp[i] >= 0) {
                        dp[i] += dp[i - dp[i]];
                    }
                } else {
                    dp[i] = 0;
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;

    }
};
